package jianzhiOffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 * @author 司松坡
 * @createTime 2023年04月07日
 */
public class Jian38 {
    public String[] permutation(String s) {
        int length = s.length();
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        boolean[] bool = new boolean[length];
        StringBuffer stringBuffer = new StringBuffer();
        List<String> res = new ArrayList<>();
        callBack(res, stringBuffer, charArray, bool, length);
        String[] resString = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resString[i] = res.get(i);
        }
        return resString;
    }

    public void callBack(List<String> res, StringBuffer stringBuffer, char[] charArray, boolean[] bool, int length) {
        if (stringBuffer.length() == length) {
            if (!res.contains(stringBuffer.toString())) {
                res.add(stringBuffer.toString());
            }
            return;
        }
        for (int i = 0; i < length; i++) {
            if (!bool[i] ) {
                if (i>2 && charArray[i-1] == charArray[i]){
                    continue;
                }
                bool[i] = true;
                stringBuffer.append(charArray[i]);
                callBack(res, stringBuffer, charArray, bool, length);
                stringBuffer.deleteCharAt(stringBuffer.length() - 1);
                bool[i] = false;
            }
        }
    }
}
